package com.demo131_分割回文串;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        if (s==null){
            return result;
        }
        if (s.length()==0){
            return result;
        }
        dfs(s,result,path,0);

        return result;
    }

    private void dfs(String s, List<List<String>> result, List<String> path, int startIndex) {
        //1.边界条件
        if (startIndex==s.length()){
            ArrayList<String> copy = new ArrayList<>();
            for (String s1 : path) {
                copy.add(s1);
            }
            result.add(copy);
            return;
        }
        //2.横向遍历
        for (int i = startIndex; i < s.length(); i++) {

            if (check(s.substring(startIndex,i+1))){
                //3.处理结果
                path.add(s.substring(startIndex,i+1));
                //4.纵向遍历
                dfs(s,result,path,i+1); // 这里纵向遍历的时候要注意: 是 i+1, 不是 startIndex +1
                //5.回溯
                path.remove(path.size()-1);
            }

        }
    }

    //辅助函数判断是否是回文串
    public boolean check(String s){
        if (s!=null&&s.length()!=0){
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)!=s.charAt(s.length()-1-i)&&i<=(s.length()-i)){
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}
